#include "types.h"
#include "defs.h"
#include "param.h"
#include "mmu.h"
#include "x86.h"
#include "proc.h"
#include "spinlock.h"
#include "sched_stride_tree.h"
#include "rq.h"
//#define QUEUE_DEBUG
//#define TICKET_DEBUG
//#define PASS_DEBUG
// by fw:

//#define RESPONSE_DEBUG

void free_rq_node(struct rq* rq, struct rq_node* node)
{
	node->left = node->right = node->parent = NULL;
	node->proc = NULL;
	node->ticket = node->stride = node->pass = 0;
	node->prev = node->next = NULL;
	rq->free_list->prev = node;
	node->next = rq->free_list;
	rq->free_list = node;
}

void tree_delete(struct rq* rq, struct proc* p)
{
	struct rq_node* parent_node = p->rq_node->parent;
	if(p->rq_node == rq->root){
		rq->root = NULL;
		free_rq_node(rq, p->rq_node); 
	}
	else{		
		if(p->rq_node == parent_node->left){			
			if(parent_node->parent == NULL ){
				rq->root = parent_node->right;
				parent_node->right->parent = NULL;
				free_rq_node(rq, parent_node);
				free_rq_node(rq, p->rq_node);
			}
			else{
				if(parent_node == parent_node->parent->left){
					parent_node->parent->left = parent_node->right;
					parent_node->right->parent = parent_node->parent;
					free_rq_node(rq, p->rq_node);
					free_rq_node(rq, parent_node);
				}
				else{
					parent_node->parent->right = parent_node->right;
					parent_node->right->parent = parent_node->parent;
					free_rq_node(rq, p->rq_node);
					free_rq_node(rq, parent_node);
				}
			}
		}
		else{
			if(parent_node->parent ==NULL ){
				rq->root = parent_node->left;
				parent_node->left->parent = NULL;
				free_rq_node(rq, parent_node);
				free_rq_node(rq, p->rq_node);
			}
			else{
				if(parent_node == parent_node->parent->left){
					parent_node->parent->left = parent_node->left;
					parent_node->left->parent = parent_node->parent;
					free_rq_node(rq, p->rq_node);
					free_rq_node(rq, parent_node);
				}
				else{
					parent_node->parent->right = parent_node->left;
					parent_node->left->parent = parent_node->parent;
					free_rq_node(rq, p->rq_node);
					free_rq_node(rq, parent_node);
				}
			}		
		}		
	}	
}

void node_modify(struct rq* rq, struct rq_node* rq_node, int delta_ticket)
{
	int old_stride,remain;
	if(rq_node == NULL)
		return;
	while(rq_node !=rq->root){
		old_stride = rq_node->stride;
		rq_node->ticket += delta_ticket;
		rq_node->stride = sched_class_stride_tree.stride1 / rq_node->ticket;

		//just consider that proc in the queue
		remain = rq_node->pass - rq->root->pass;
		remain = remain * rq_node->stride / old_stride;
		rq_node->pass = rq->root->pass + remain;

		rq_node = rq_node->parent;
	}
	old_stride = rq_node->stride;
	rq_node->ticket += delta_ticket;
	rq_node->stride = sched_class_stride_tree.stride1 / rq_node->ticket;
}
int node_entitled(struct rq_node *node)
{
	return (node->stride - node->proc->remain) * sched_class_stride_tree.timeslice / node->stride;
}
void pseudo_allocate(struct rq* rq,struct rq_node *node, int elapsed)
{
	if(node == NULL)
		return;
	for(;node != rq->root; node = node->parent){
		node->pass += node->stride * elapsed / sched_class_stride_tree.timeslice;
	}
}
struct rq_node* get_free_node(struct rq* rq)
{
	struct rq_node *node = rq->free_list;
	rq->free_list = rq->free_list->next;
	if(rq->free_list != NULL)
	{
	    rq->free_list->prev = NULL;
	}
	node->next = node->prev = NULL;
	node->left = node->right = node->parent = NULL;
	node->proc = NULL;
	node->ticket = 0;
	node->stride = 0;
	node ->pass = 0;
	return node;
}
void tree_insert(struct rq* rq, struct proc* p)
{
	struct rq_node* new_node = get_free_node(rq);
	//pay attention to that replaced node's proc!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
	new_node->proc = p;
	p->rq = rq;
	p->rq_node = new_node;
	new_node->ticket = p->ticket;
	new_node->pass = p->pass;
	new_node->stride = p->stride;


	if(rq->root == NULL){
		//when rq is empty
	    rq->root = new_node;
	}	
	else{
		struct rq_node* parent_node = get_free_node(rq);
		struct rq_node* tmp_node = NULL;
		for(tmp_node = rq->root; tmp_node->left != NULL && tmp_node->right != NULL;){
			if(tmp_node->left->ticket > tmp_node->right->ticket)
				tmp_node = tmp_node->right;
			else
				tmp_node = tmp_node->left;
		}
		if(tmp_node == rq->root){
			rq->root = parent_node;
			parent_node->left = tmp_node;
			parent_node->ticket = tmp_node->ticket;
			parent_node->pass = tmp_node->pass;
			parent_node->stride = tmp_node->stride;
			parent_node->right = new_node;
			tmp_node->parent = parent_node;
			new_node->parent = parent_node;
			tmp_node->left = NULL;
			tmp_node->right = NULL;
		}
		else{
			if(tmp_node == tmp_node->parent->left){
				tmp_node->parent->left = parent_node; 
			}
			else{
				tmp_node->parent->right = parent_node;				 
			}
			parent_node->parent = tmp_node->parent;
			parent_node->left = tmp_node;
			parent_node->ticket = tmp_node->ticket;
			parent_node->pass = tmp_node->pass;
			parent_node->stride = tmp_node->stride;
			parent_node->right = new_node;
			tmp_node->parent = parent_node;
			new_node->parent = parent_node;
			tmp_node->left = NULL;
			tmp_node->right = NULL;
		}		
	}
}

void init_rq_stride_tree(struct rq* rq){
  int i;

  rq->root = NULL;

  //init first element and free_list head
  rq->nodes[0].proc = NULL;
  rq->nodes[0].prev = NULL;
  rq->nodes[0].next = &(rq->nodes[1]);
  rq->free_list = &(rq->nodes[0]);

  //mark nodes from 1 to NPROC -1 free and linked
  for(i = 1; i < NPROC - 1; i++){
    rq->nodes[i].proc = NULL;
	rq->nodes[i].prev = &(rq->nodes[i-1]);
	rq->nodes[i].next = &(rq->nodes[i+1]);
  }

  //mark last node free and linked
  rq->nodes[i].prev = &(rq->nodes[i-1]);
  rq->nodes[i].next = NULL;

  rq->proc_num = 0;

}

void enqueue_proc_stride_tree(struct rq* rq, struct proc *p){

  (rq->proc_num)++;

  //insert p into rq in ascending order of pass value
  tree_insert(rq, p);
  node_modify(rq, p->rq_node->parent, p->ticket);
  pseudo_allocate(rq, p->rq_node->parent, -node_entitled(p->rq_node));
  if(p != rq->root->proc)
  p->pass = rq->root->pass + p->remain;
  p->rq_node->pass = p->pass;

}

//pay attention this func doesn't change p's state and p's state mustn't be running
//pay attention this func doesn't change p's state and p's state mustn't be running
void dequeue_proc_stride_tree(struct rq *rq, struct proc *p){

  p->remain = p->pass - rq->root->pass;
  pseudo_allocate(rq, p->rq_node->parent, node_entitled(p->rq_node));
  node_modify(rq, p->rq_node->parent, -p->ticket);
  tree_delete(rq, p);
  (rq->proc_num)--;
}


//when idle yields, do nothing. return to yield() to handle;
//when normal proc yields, re_insert into the rq
//***However this can cause this very proc be picked again!!! instead of chose another***
//proc's state doesn't change
void yield_proc_stride_tree(struct rq *rq){
	struct proc* p = cp; //pay attention to cp ,this maybe dangerous when current proc changes! esp when interrupt is on

	//here use debug information, not a good way.
	if(p == idleproc[cpu()]){
	   return;
	}
	else{
	   struct rq_node* node = p->rq_node;
	   do{
		   node->pass += node->stride * (p->timeslice - p->timeleft) / p->timeslice;
		   node = node->parent;
	   }while(node != NULL);

	   p->pass = p->rq_node->pass;
	   if(p->timeleft == 0)
	      p->timeleft = p->timeslice;
	   return;
	}
	
}

struct proc* pick_next_proc_stride_tree(struct rq *rq){
  //pay attenion rq->head doesn't change when return
  struct rq_node* node = rq->root;
  if(node == NULL)
	  return NULL;
  else{
	  while(node->left != NULL && node->right !=NULL){
		  if(node->left->pass > node->right->pass){
			  node = node->right;
		  }
		  else{
			  node = node->left;
		  }
	  }
	  return node->proc;
  }
}

#ifdef RESPONSE_DEBUG
 int now;
 int response[1000] = {0};
 int last_tick = 0;
#endif
void proc_tick_stride_tree(struct rq* rq, struct proc* p){
   if(p == idleproc[cpu()]){
       //pay attention to the state of the proc
	   yield();
   }else{
      p->timeleft--;
#ifdef TICK_DEBUG
	  cprintf("proc pid=%d tick_interrupt with timeleft=%d\n", p->pid, p->timeleft);
#endif
      if(p->timeleft == 0){
#ifdef RESPONSE_DEBUG
		  if(p->pid == 10){
			  acquire(&tickslock);
			  now = ticks;
			  release(&tickslock);
			  if(last_tick == 0){
				  last_tick = now;
			  }
			  else{
				  response[now - last_tick]++;
				  last_tick = now;
			  }
		  }
#endif
      yield();
      }
   }
}



const struct sched_class sched_class_stride_tree = {
  .init_rq		= init_rq_stride_tree,
  .enqueue_proc		= enqueue_proc_stride_tree,
  .dequeue_proc		= dequeue_proc_stride_tree,
  .yield_proc		= yield_proc_stride_tree,
  .pick_next_proc	= pick_next_proc_stride_tree,
  .proc_tick		= proc_tick_stride_tree,
  .stride1          = 100000000,
  .timeslice        = 5
  //.load_balance		= load_balance_simple,
  //.get_proc		= get_proc_simple,
};

